
# print("重复的子字符串")
def repeat_child_str(s:str)->bool:
    for i in range(1,len(s)):
        flag=len(s)%len(s[0:i])
        child_count=len(s)//len(s[0:i])
        if flag==0:
            tem = s[::1]
            for j in range(0,child_count):
                tem=tem.replace(s[0:i],"")
            if len(tem)==0:
                return True
    return False


print("分饼干")
def fenbinggan(g:list[int],s:list[int])->int:
    ng=len(g)
    ns=len(s)
    g.sort()
    s.sort()
    res,child,cooki=0,0,0
    while child<ng and cooki<ns:
        if g[child]<=s[cooki]:
            res=res+1
            child=child+1
            cooki=cooki+1
        else:
            cooki=cooki+1
    return res




print("找到所有数组中消失的数字")
def xiaoshideshuzi(nums:list[int]) ->list[int]:
    # res=[]
    # for i in range(1,len(nums)+1):
    #     if i not in nums:
    #         res.append(i)
    # return res
    res=[]
    import collections
    count=collections.Counter(nums)
    for i in range(1,len(nums)+1):
        if count[i] ==0:
            res.append(i)
    return res



print("排列硬币")
def pailieyingbi(n:int)->int:
    if n==0 or n==1:
        return n
    sum=0
    for i in range(1,n+1):
        sum=sum+i
        if sum==n:
            return i
        if sum>n:
            return i-1





print("字符串相加"
      "给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回"
      "你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式")
def addStrings2(num1:str,num2:str)->str:
    res=""
    i,j,jinwei=len(num1)-1,len(num2)-1,0
    while i>=0 or j>=0:
        n1=int(num1[i]) if i>=0 else 0
        n2=int(num2[j]) if j>=0 else 0
        tem=n1+n2+jinwei
        jinwei=tem//10
        res=str(tem%10)+res
        i=i-1
        j=j-1
    if jinwei >0:
        return str(jinwei)+res
    else:
        return res
def addStrings(nums1:str,nums2:str)->str:
    i,j,carry=len(nums1)-1,len(nums2)-1,0
    res=""
    while i>=0 or j>=0:
        n1=int(nums1[i]) if i>=0 else 0
        n2=int(nums2[j]) if j>=0 else 0
        tem=n1+n2+carry
        carry=tem//10
        res=str(tem%10)+res
        i=i-1
        j=j-1
    if carry:
        return "1"+res
    else:
        return res




print("给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。")
def thirdMax(nums:list)->int:
    nums = list(set(nums))
    # nums.sort()
    if len(nums) <3:
        return nums[-1]
    else:
        return nums[-3]

thirdMax([2,2,3,1])

print("给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的 回文串的长度")
def longesthuiwenchuan(s:str)->int:
    import collections
    counter = dict(collections.Counter(s))
    # res,odd=0,0
    # for count in counter.values():
    #     tem=count%2
    #     res = res+(count-tem)
    #     if tem==1:
    #         odd=1
    # return res+odd
    if len(set(list(s)))==1:
        return len(s)
    res=0
    tem=0
    for k,v in counter.items():
        if v%2 ==0:
            res = res+v
        if v%2==1:
            res = res+(v//2)*2
            tem=1
    return res+tem




print("计算所有左叶子节点之和")
class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=0
        self.left=left
        self.right=right
def sumOfLeftLeaves(root:TreeNode)->int:
    res=[]
    def inner(node:TreeNode):
        if not node:
            return 0
        if node.left and not node.left.left and not node.left.right:
            # nonlocal res
            res.append(node.left.val)
        inner(node.left)
        inner(node.right)
    inner(root)
    return sum(res)



print("给定字符串 s 和 t ，判断 s 是否为 t 的子序列"
      "字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。"
      "（例如，'ace'是'abcde'的一个子序列，而'aec'不是）")
def isSubsequence(s:str,t:str)->bool:
    if s is None:
        return True
    i=0
    for c in t:
        if s[i]==c:
            i=i+1
            if len(s)==i:
                return True
    return False




print("给定两个字符串 s 和 t ，它们只包含小写字母"
      "字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母"
      "请找出在 t 中被添加的字母。")
def findDifferent(s:str,t:str)->str:
    import collections
    return list(collections.Counter(t)-collections.Counter(s))[0]


print("给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成")
def can_construct(ransomNote:str,magazine:str)->bool:
    import collections
    dictm=collections.Counter(magazine)
    for r in ransomNote:
        dictm[r]=dictm[r]-1
        if dictm[r]<0:
            return False
    return True



print("有效的完全平方数")
def isyouxiaowanquanpingfangshu(num:int)->bool:
    if num<0:
        return False
    if num==0 or num==1:
        return True
    for i in range(1,num):
        if i**2 == num:
            return True
        if i**2<num and (i+1)**2>num:
            return False


print("输出两个元素的交集")
def intersection(nums1:list[int],nums2:list[int])->list[int]:
    # return list(set(nums1)&set(nums2))
    return list(set(nums1).intersection(set(nums2)))


print("反转字符串中的元音字母")
def reverseVowels(s:str)->str:
    l,r=0,len(s)-1
    chars=list(s)
    vowels=set("aeiouAEIOU")
    while l<r:
        if chars[l] not in vowels:
            l=l+1
        elif chars[r] not in vowels:
            r=r-1
        else:
            chars[l],chars[r] = chars[r],chars[l]
            l=l+1
            r=r-1
    return "".join(chars)



print("4的幂")
def isPower4(n:int)->bool:
    if n<=0:
        return False
    if n==1:
        return True
    res = 1
    while n>=2:
        res=res*4
        if res == n:
            return True
        if res>n:
            return False



print("nim游戏")
def xinnim(n:int)->bool:
    return n%4!=0




pattern="abbaa"
sp=["dog","cat","cat","dog","fish"]
print(zip(pattern,sp))
print(dict(zip(pattern,sp)))
for c,st in zip(pattern,sp):
    print(c,st)

print("给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律")
def wordPattern(pattern:str,s:str)->bool:
    sp=s.split(" ")
    if len(pattern) != len(sp):
        return False
    map1=dict()
    map2=dict()
    for c,st in zip(pattern,sp):
       if c in map1:
           if map1[c] !=st:
               return False
       else:
           map1[c] =st
       if st in map2:
           if map2[st] !=c:
               return False
       else:
           map2[st] = c
    return True




print("第一个错误的版本")
# def firstBadVersion(n:int) ->int:
#     i,j=1,n
#     while i<=j:
#         mid = (i+j)//2
#         if isBadVersion(mid):
#             j=mid-1
#         else:
#             i=mid+1
#     return i




print("判断是不是丑数")
def isUgly(n:int)->bool:
    if n <=0:
        return False
    factors = [2,3,5]
    for f in factors:
        while n%f==0:
            n=n//f
    if n==1:
        return True
    else:
        return False




print("两个栈实现队列")
class MyQueue:
    def __init__(self):
        self.st1=[]
        self.st2=[]
    def push(self,x:int):
        self.st1.append(x)
    def pop(self)->int:
        # 注意此处只能用if not self.st2  或 if len(self.st2)==0   不能用 if self.st2  is None  因为初始化的时候已经定义为空列表了
        if len(self.st2) ==0:
            self.export()
        x=self.st2.pop()
        return x
    def peek(self) -> int:
        if len(self.st2) ==0:
            self.export()
        return self.st2[-1]
    def empty(self) ->bool:
        if self.st1 or self.st2:
            return False
        return True

    def export(self):
        while self.st1:
            x=self.st1.pop()
            self.st2.append(x)


print("2的幂次方")
def isPowerOf2(n:int)->bool:
    if n<=0:
        return False
    res = 1
    while True:
        if n==1:
            return True
        res = res*2
        if res == n:
            return True
        if res >n:
            return False




print("反转二叉树")
class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
def invertTree(root:TreeNode)->TreeNode:
    if root is None:
        return
    left = invertTree(root.left)
    right=invertTree(root.right)
    root.left=right
    root.right=left
    return root




print("同构字符串")
def tonggoustr(s:str,t:str)->bool:
    import collections
    dicts=collections.Counter(s)
    dictt=collections.Counter(t)
    if list(dicts.values()) != list(dictt.values()):
        return False
    for i in range(0,len(s)):
        inds = list(dicts.keys()).index(s[i])
        if list(dictt.keys())[inds] != t[i]:
            return False
    return True



print("请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。")
class MyStack:
    def __init__(self):
        self.stack=[]
    def push(self,x:int):
        self.stack.append(x)
    def pop(self)->int:
        # tp = self.stack.pop()
        return self.stack.pop()
    def top(self):
        return self.stack[-1]
    def empty(self):
        return len(self.stack) == 0



print("完全二叉树的节点个数")
class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=0
        self.left=left
        self.right=right
def count_node(root:TreeNode)->int:
    if root is None:
        return 0
    return count_node(root.left)+count_node(root.right)+1




print("存在重复元素二"
      "给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，"
      "满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false")
def containk(nums:list[int],k:int)->bool:
    for i in range(0,len(nums)):
        for j in range(0,len(nums)):
            if nums[i] == nums[j] and abs(i-j)<=k and i!=j:
                print(nums[i],nums[j],i,j)
                return True
    return False
containk([1,2,3,1,2,3],2)

def containk2(nums:list[int],k:int)->bool:
    # 存储以enumerate()返回值的值为键  以enumerate()返回值的键为值
    num_index={}
    for index,num in enumerate(nums):
        if num in num_index and abs(index-num_index[num]) <=k:
            return True
        num_index[num] = index
    return False

print("环形链表"
      "如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环")
class ListNode:
    def __init__(self,val=0,next=None):
        self.val=0
        self.next=next
def hasCycle(head:ListNode) ->bool:
    if head is None:
        return None
    fast=head
    slow=head
    while True:
        if fast is None or fast.next is None:
            return False
        fast=fast.next.next
        slow=slow.next
        if fast==slow:
            return True





print("路径总和"
      "给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，"
      "这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。")
class TreeNode:
    def __init__(self,val,left,right):
        self.val = val
        self.left=left
        self.right=right
def hasPathSum(root:TreeNode,targetSum:int) ->bool:
    if not root:
        return False
    targetSum = targetSum-root.val
    if not root.left and not root.right:
        return targetSum == 0
    else:
        return hasPathSum(root.left,targetSum) or hasPathSum(root.right,targetSum)





print("判定是不是平衡二叉树"
      "平衡二叉树：二叉树的每个节点的左右子树的高度差的绝对值不超过 1，则二叉树是平衡二叉树。"
      "根据定义，一棵二叉树是平衡二叉树，当且仅当其所有子树也都是平衡二叉树，"
      "因此可以使用递归的方式判断二叉树是不是平衡二叉树，递归的顺序可以是自顶向下或者自底向上")
class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
def isBalanced(root:TreeNode) ->bool:
    "判定是不是平衡二叉树"
    "平衡二叉树：二叉树的每个节点的左右子树的高度差的绝对值不超过 1，则二叉树是平衡二叉树。"
    "根据定义，一棵二叉树是平衡二叉树，当且仅当其所有子树也都是平衡二叉树，"
    "因此可以使用递归的方式判断二叉树是不是平衡二叉树，递归的顺序可以是自顶向下或者自底向上"
    def height(node:TreeNode):
        if node is None:
            return 0
        return max(height(node.left),height(node.right))+1
    if root is None:
        return True
    else:
        return abs(height(root.left)-height(root.right))<=1 and isBalanced(root.left) and isBalanced(root.right)





print("合并两个有序链表")
class ListNode:
    def __init__(self,val,next=None):
        self.val = val
        self.next = next


def hebingyouxulianbiao(list1:ListNode,list2:ListNode) ->ListNode:
    if list1 is None and list2 is None:
        return None
    if list1 is None:
        return list2
    if list2 is None:
        return list1
    new_head = ListNode()
    current = new_head
    while list1 and list2:
        if list1.val>=list2.val:
            current.next=list2
            list2=list2.next
        else:
            current.next=list1
            list1=list1.next
        current=current.next
    if list1 is None:
        current.next=list2
    if list2 is None:
        current.next=list1



def maopao(target:list):
    for i in range(0,len(target)):
        for j in range(0,len(target)-1-i):
            if target[j]>target[j+1]:
                # target[j],target[j+1]=target[j+1],target[j]
                tem=target[j]
                target[j]=target[j+1]
                target[j+1]=tem
    print(target)
target=[5,3,2,1,12,2,5]
maopao(target)


